<?php

class Bus_Model_PathFinder
{
    private $_routeMap;

    public function  __construct()
    {
        $modelStop = new Bus_Model_Stop();

        $stops = $modelStop->fetchAll();
        
        $modelRoute = new Bus_Model_Route();
        $routes = $modelRoute->fetchAll();

        $stopIds = array();
        $stopIds = array();
        $priceMap = array();
        $rMap = array();
        foreach ($routes as $route) {
            $priceMap[$route->bus_stop_sid_from][$route->bus_stop_sid_to] = 1;
            $priceMap[$route->bus_stop_sid_from][$route->bus_stop_sid_from] = 0;

            if (!in_array($route->bus_stop_sid_from, $stopIds)) {
                $stopIds[] = $route->bus_stop_sid_from;
            }
            if (!in_array($route->bus_stop_sid_to, $stopIds)) {
                $stopIds[] = $route->bus_stop_sid_to;
            }
            $rMap[$route->bus_stop_sid_from][$route->bus_stop_sid_to] = $route->bus_stop_sid_from;
        }
        foreach ($stopIds as $from) {
            foreach ($stopIds as $to) {
                if (!isset($priceMap[$from][$to])) {
                    $priceMap[$from][$to] = 1000000;
                }
            }
        }

        $newPriceMap = $priceMap;
        foreach ($stopIds as $k) {
            foreach ($priceMap as $i => $values) {
                foreach ($values as $j => $cnt) {
                    if (isset($priceMap[$i][$k]) && isset($priceMap[$k][$j]) &&
                        ($priceMap[$i][$k] + $priceMap[$k][$j]) < $cnt) {
                        $newPriceMap[$i][$j] = $priceMap[$i][$k] + $priceMap[$k][$j];
                        $rMap[$i][$j] = $k;
                    }
                }
            }
            $priceMap = $newPriceMap;
        }
        $this->_routeMap = $rMap;
    }

    public function getRouteMap()
    {
        return $this->_routeMap;
    }

    public function getPath($from, $to)
    {
        if (!isset($this->_routeMap[$from][$to])) {
            return false;
        }
        $pathItems = array($to);
        $i = 0;
        while (true) {
            if (++$i > 1000) {
                return 'Incorrect algorithm';
            }
            $pathItems[] = $this->_routeMap[$from][$to];
            $to = $this->_routeMap[$from][$to];
            if ($to == $from) {
                break;
            }
        }
        return array_reverse($pathItems);
    }
}